package com.congee02.template.graph;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class TopologicalSort {

    // https://leetcode.cn/problems/course-schedule/description/
    public List<Integer> topological(List<Integer>[] graph) {


        List<Integer> ans = new ArrayList<>();

        int n = graph.length;

        int[] ins = new int[n];

        for (List<Integer> tos : graph) {
            if (tos == null) {
                continue;
            }
            for (int to : tos) {
                ins[to] ++;
            }
        }

        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 0 ; i < n ; i ++ ) {
            if (ins[i] == 0) {
                q.offer(i);
            }
        }

        while (! q.isEmpty()) {

            int sz = q.size();
            for (int i = 0 ; i < sz ; i ++ ) {

                int cur = q.poll();
                ans.add(cur);
                if (graph[cur] == null) {
                    continue;
                }
                for (int next : graph[cur]) {
                    ins[next] --;
                    if (ins[next] == 0) {
                        q.offer(next);
                    }
                }

            }

        }

        // 如果有任一节点的入度依旧 > 0，则该图有环
//        for (int x : ins) {
//            if (x > 0) {
//                // has cycle
//            }
//        }

        return ans;

    }

}
